' Written by Craig'n'Dave
Module Module1
    ' Binary tree using objects
    Public Class Binary_tree
        Public Class Node
            Public data As String
            Public left_pointer As Node
            Public right_pointer As Node
        End Class

        Public root As Node

        Function add(item As String)
            'Check memory overflow
            Try
                Dim new_node As New Node
                new_node.data = item
                Dim current_node As Node = root
                new_node.left_pointer = Nothing
                new_node.right_pointer = Nothing
                ' Tree is empty
                If IsNothing(current_node) Then
                    root = new_node
                Else
                    ' Find correct position in the tree
                    Dim previous As Node = Nothing
                    While Not IsNothing(current_node)
                        previous = current_node
                        If item < current_node.data Then
                            current_node = current_node.left_pointer
                        Else
                            current_node = current_node.right_pointer
                        End If
                    End While
                    If item < previous.data Then
                        previous.left_pointer = new_node
                    Else
                        previous.right_pointer = new_node
                    End If
                End If
                Return True
            Catch
                Return False
            End Try
        End Function

        Sub delete(item As String)
            ' Using Hibbard's algorithm (leftmost node of right sub-tree is the successor)
            ' Find the node
            Dim current_node As Node = root
            Dim previous As Node = Nothing
            While Not IsNothing(current_node) And current_node.data <> item
                previous = current_node
                If item < current_node.data Then
                    current_node = current_node.left_pointer
                Else
                    current_node = current_node.right_pointer
                End If
            End While

            ' Handle 3 cases depending on the number of child nodes
            If Not IsNothing(current_node) Then
                If IsNothing(current_node.left_pointer) And IsNothing(current_node.right_pointer) Then
                    ' Node has no children
                    If previous.data > current_node.data Then
                        previous.left_pointer = Nothing
                    Else
                        previous.right_pointer = Nothing
                    End If
                ElseIf IsNothing(current_node.right_pointer) Then
                    ' Node has one left child
                    If previous.data > current_node.data Then
                        previous.left_pointer = current_node.left_pointer
                    Else
                        previous.right_pointer = current_node.left_pointer
                    End If
                ElseIf IsNothing(current_node.left_pointer) Then
                    ' Node has one right child
                    If previous.data > current_node.data Then
                        previous.left_pointer = current_node.right_pointer
                    Else
                        previous.right_pointer = current_node.right_pointer
                    End If
                Else
                    ' Node has two children
                    Dim right_node As Node = current_node.right_pointer
                    If Not IsNothing(right_node.left_pointer) Then
                        ' Find the smallest value in the right sub-tree
                        Dim smallest As Node = current_node.right_pointer
                        While Not IsNothing(smallest.left_pointer)
                            previous = smallest
                            smallest = smallest.left_pointer
                        End While
                        ' Change the deleted node value to the smallest value
                        current_node.data = smallest.data
                        ' Remove the successor node
                        previous.left_pointer = Nothing
                    Else
                        ' Handle special case of no left sub-tree from right node
                        current_node.data = right_node.data
                        current_node.right_pointer = Nothing
                    End If
                End If
            End If
        End Sub

        Sub preorder(current_node As Node)
            If Not IsNothing(current_node) Then
                ' Visit each node: NLR
                Console.WriteLine(current_node.data)
                If Not IsNothing(current_node.left_pointer) Then
                    preorder(current_node.left_pointer)
                End If
                If Not IsNothing(current_node.right_pointer) Then
                    preorder(current_node.right_pointer)
                End If
            End If
        End Sub

        Sub inorder(current_node As Node)
            If Not IsNothing(current_node) Then
                ' Visit each node: LNR
                If Not IsNothing(current_node.left_pointer) Then
                    inorder(current_node.left_pointer)
                End If
                Console.WriteLine(current_node.data)
                If Not IsNothing(current_node.right_pointer) Then
                    inorder(current_node.right_pointer)
                End If
            End If
        End Sub

        Sub postorder(current_node As Node)
            If Not IsNothing(current_node) Then
                ' Visit each node: LRN
                If Not IsNothing(current_node.left_pointer) Then
                    postorder(current_node.left_pointer)
                End If
                If Not IsNothing(current_node.right_pointer) Then
                    postorder(current_node.right_pointer)
                End If
                Console.WriteLine(current_node.data)
            End If
        End Sub

        Sub bft(current_node As Node)
            Dim q = New Queue()
            Do While Not IsNothing(current_node)
                Console.WriteLine(current_node.data)
                If Not IsNothing(current_node.left_pointer) Then
                    q.Enqueue(current_node.left_pointer)
                End If
                If Not IsNothing(current_node.right_pointer) Then
                    q.Enqueue(current_node.right_pointer)
                End If
                If q.Count > 0 Then current_node = q.Dequeue() Else current_node = Nothing
            Loop
        End Sub
    End Class

    ' Main program starts here
    Sub Main()
        Dim items() As String = {"E", "B", "G", "A", "C", "F", "H"}
        ' Create binary tree
        Dim binary_tree As New Binary_tree
        For index = 0 To items.Length - 1
            binary_tree.add(items(index))
        Next
        ' Traverse the binary tree
        Console.WriteLine("Breadth first traversal:")
        binary_tree.bft(binary_tree.root)
        Console.WriteLine("Pre-order traversal:")
        binary_tree.preorder(binary_tree.root)
        Console.WriteLine("In-order traversal:")
        binary_tree.inorder(binary_tree.root)
        Console.WriteLine("Post-order traversal:")
        binary_tree.postorder(binary_tree.root)
    End Sub

End Module